/*
 * @lc app=leetcode.cn id=42 lang=cpp
 * @lcpr version=30204
 *
 * [42] 接雨水
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n-1;
        int prevMax = 0, sufMax = 0;
        int total = 0;
        // 这个题的关键就是当前位置能接雨水就需要左右两边的高度大于现在的高度，且取左右两边最小的那个作为接水的高度
        // 左右指针向中间移动，每个元素都遍历了一遍，O(N)，就算是没有接到雨水也进行计算，只不过结果为0
        while(left <= right)
        {
            prevMax = max(prevMax, height[left]);
            sufMax = max(sufMax, height[right]);
            // 这里先算当前最小的那边，小的能限制住接水的量，确保不会出现遗漏
            if(prevMax < sufMax)
            {
                total += prevMax - height[left++];
            }
            else
            {
                total += sufMax - height[right--];
            }
        }
        return total;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [0,1,0,2,1,0,1,3,2,1,2,1]\n
// @lcpr case=end

// @lcpr case=start
// [4,2,0,3,2,5]\n
// @lcpr case=end

 */

